#include <iostream>
using namespace std;

using ll = long long;
ll mod_pow(ll a, ll b, ll mod){
    ll res = 1;
    while(b > 0){
        if (b & 1){
            res = res * a % mod;
        }
        a = a*a%mod;
        b >>= 1;
    }
    return res;
}
int main() {
    int q;
    int a,b,p;
    cin>>q;
    for(int i = 0; i < q; i++){
        cin>>a>>b>>p;
        cout<<mod_pow(a, b, p)<<endl;
    }
    
}
// 64 位输出请用 printf("%lld")